package leetcode.interviewClassics;

import java.util.Stack;

/**
 * @author Cheng Jun
 * Description: 请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。
 * 链接：https://leetcode-cn.com/problems/min-stack-lcci
 * @version 1.0
 * @date 2021/11/4 13:17
 * @see MinStack
 * 提交 LeetCode会报错。int x 超出边界报错。网上说的 空间复杂度O(1) 解法的前提是 插入的元素有一定的范围比如 【-1000， +1000】
 */
public class MinStack1 {

    // 注意：保存 插入值x 和min 的差
    private Stack<Integer> stack = new Stack<>();
    // 保存 栈元素中的最小值
    private int min;

    /**
     * initialize your data structure here.
     */
    public MinStack1() {
    }

    public static void main(String[] args) {
        MinStack1 minStack1 = new MinStack1();
        minStack1.push(1);
        minStack1.push(2);
        minStack1.top();
        minStack1.getMin();
        minStack1.pop();
        minStack1.getMin();
        minStack1.top();
    }

    public void push(int x) {
        // 空栈
        if (stack.isEmpty()) {
            min = x;
            stack.push(x);
        } else {
            stack.push(x - min);
            min = x - min < 0 ? x : min;
        }
    }

    public void pop() {
        if (stack.peek() < 0) {
            min = min - stack.peek();
            stack.pop();
        } else {
            stack.pop();
        }
    }

    public int top() {
        if (stack.peek() < 0) {
            return min;
        } else {
            // 注意如果 stack 的元素只有一个 就不能做加法运算了。
            // （Stack底层是数组实现的，不是链表实现，所以size() 方法的空间复杂度是 O(1) ）
            if (stack.size() == 1) return min;
            else return min + stack.peek();
        }
    }

    public int getMin() {
        return min;
    }
}
